package com.ljy.my_study.lintcode.回文;

import java.util.HashSet;
import java.util.Set;

/** 
* @author James
* @date 2018年4月12日 
*/
public class PalindromeMain {
	//找出回文中心点的索引，然后以中心点的两边字符一步步作对比
	public static String palindrome(String str) {
		if(str.length()==0||str.length()==1) {
			return str;
		}
		String maxStr="";
		char[] array=str.toCharArray();
		for(int i=1;i<array.length-1;i++) {
			if(array[i-1]==array[i+1]) {
				String s=compareByIndexSet(i,array,str);
				if(s.length()>maxStr.length()) {
					maxStr=s;
				}
			}
		}
		for(int i=0;i<array.length-1;i++) {
			if(array[i]==array[i+1]) {
				String s=compareByIndex2Set(i,array,str);
				if(s.length()>maxStr.length()) {
					maxStr=s;
				}
			}
		}
		return maxStr;
	}
	
	public static String compareByIndexSet(int index,char[] array,String str) {
		int startIndex=index-1;
		int endIndex=index+1;
		
		while(array[startIndex]==array[endIndex]) {
			startIndex--;
			endIndex++;
			if(!(startIndex>=0&&endIndex<=array.length-1)) {
				startIndex++;
				endIndex--;
				break;
			}
		}
		if(array[startIndex]!=array[endIndex]) {
			startIndex++;
			endIndex--;
		}
		return str.substring(startIndex, endIndex+1);
	}
	public static String compareByIndex2Set(int index,char[] array,String str) {
		int startIndex=index;
		int endIndex=index+1;
		
		while(array[startIndex]==array[endIndex]) {
			startIndex--;
			endIndex++;
			if(!(startIndex>=0&&endIndex<=array.length-1)) {
				startIndex++;
				endIndex--;
				break;
			}
		}
		if(array[startIndex]!=array[endIndex]) {
			startIndex++;
			endIndex--;
		}
		return str.substring(startIndex, endIndex+1);
	}
	
	public static void main(String[] args) {
		String maxStr=palindrome("a");
		System.out.println(maxStr);
	}
}
